package com.itheima.Array.BinarySearch;

/**
 * @Author: Ethan Yankang
 * @Program: code-random-recordings
 * @Date: 2024-07-28 10:35
 **/
public class SearchRange {

    int leftBorder=-1;
    int rightBorder=-1;

    public int[] searchRange(int nums[]  ,int target) {
        int length = nums.length;
//        先判断特殊情况.在两边的情况去除之
        if(length==0)return new int[]{-1,-1};
        if(target < nums[0] || target > nums[length - 1]) return new int[]{-1, -1};

//        在判断中间的情况，有就返回范围，没有就返回[-1,-1],显然用while。
//        这里分而治之，左右边界分开查找

        leftBorder = getLeftBorder(nums, target);
        rightBorder = getRightBorder(nums, target);
        // 这里一定要判断(rightBorder-leftBorder>1)，因为如果target没有的话，会出现RB<LB的情况，而这种情况，返回[-1,-1]
        // 例如 1 2 3 5 6 判断4  ==》边界范围是RB=2，值为3；LB=3，值为5，所以是[3,2]显然是错的。
        // 这里正确答案+1，-1的情况是因为跳出循环的时候索引处一定不是本元素
        return (rightBorder-leftBorder>1)?new int[]{leftBorder+1, rightBorder-1}:new int[]{-1,-1};
    }

    /*
     * @description 用户查找左边界的索引.而且这里的左边索引的寻找条件就是
     * if(nums[mid]>=target) {
     * right=mid-1,
     * leftBorder=right;
     * }
     * 这里就体现了二分法的精髓，一直寻找最符合条件，直至不符合为止，这里我们的条件一定会不满足，因为两个if是全集
     * @params
     * @return 左边界的索引
     */
    private int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] >= target) {
                right = mid - 1;
                leftBorder = right;
            } else {
                left = mid + 1;
            }
        }
        return leftBorder;
    }


    /*
     * @description 用户查找右边界的索引.而且这里的右边索引的寻找条件就是
     * if(nums[mid]<=target) {
     * left=mid+1,
     * rightBorder=left;
     * }
     * 这里就体现了二分法的精髓，一直寻找最符合条件，直至不符合为止，这里我们的条件一定会不满足，因为两个if是全集
     * @params
     * @return 右边界的索引
     */
    private int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] <= target) {
                left = mid + 1;
                rightBorder=left;
            } else {
                right = mid - 1;
            }
        }

        return rightBorder;
    }

}
